package com.yehui.algorithm.dp.backpack;

/**
 * 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件，每件费用是c[i]，价值是w[i]。
 * 求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
 *
 * dp(i,t) = max{dp(i-1, t - V[i] * k) + P[i] * k}; （0 <= k <= M[i] && 0 <= k * V[i] <= t）
 *
 * @author 业徽
 * @date 2021/2/9
 */
public class MultiBackpack {

    /**
     * 根据递推公式
     *
     * @param V
     * @param C
     * @param W
     * @param M 数量限制
     * @return
     */
    public int normal(int V, int[] C, int[] W, int[] M) {
        int[][] dp = new int[C.length + 1][V + 1];

        for (int i = 1; i <= C.length; i++) {
            for (int j = 1; j <= V; j++) {
                for (int k = 0; k * C[i - 1] <= j && k <= M[i - 1]; k++) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * C[i - 1]] + k * W[i - 1]);
                }
            }
        }

        return dp[C.length][V];
    }

    public int optSpace(int V, int[] C, int[] W, int[] M) {
        int[] dp = new int[V + 1];
        for (int i = 0; i < C.length; i++) {
            for (int j = C[i]; j <= V && j <= C[i] * M[i]; j++) {
                dp[j] = Math.max(dp[j], dp[j - C[i]] + W[i]);
            }
        }

        return dp[V];
    }

}
